package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * 两个有序链表合并
 * 合并前：1 ->3 ->3 ->5 ->7    2 ->2 ->3 ->3 ->7
 * 合并后：1 ->2 ->2 ->3 ->3 ->3 ->3 ->5 ->7
 */
public class Code08_SortLinkedMerge {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 3, 4, 5, 7};
        int[] arr2 = new int[]{2, 2, 5, 6, 7};
        ListNode head1 = ListNodeUtils.getLinked(arr1);
        ListNode head2 = ListNodeUtils.getLinked(arr2);
        ListNode merge = merge(head1, head2);
        ListNodeUtils.print(merge);
    }

    public static ListNode merge(ListNode head1, ListNode head2) {
        // 如果链表有为空的，则返回链表
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        // 用最小的head作为返回总头
        ListNode shead = head1.val <= head2.val ? head1 : head2; // 1
        ListNode cur1 = shead.next; // 1-> 3
        ListNode cur2 = shead == head1 ? head2 : head1; // 2

        // pre 被初始化为合并链表的头节点 shead。
        ListNode last = shead;
        while (cur1 != null && cur2 != null) {
            if (cur1.val >= cur2.val) {
                last.next = cur2;
                cur2 = cur2.next;
            } else {
                last.next = cur1;
                cur1 = cur1.next;
            }
            /**
             * last = last.next;：
             * 在将节点添加到合并链表之后，last 要更新为新的尾部节点，即 last.next。
             * 这样，在下一次循环时，last 就会指向当前合并链表的最后一个节点，以便我们可以继续添加新的节点。
             */
            last = last.next;
        }
        // 是将剩余未处理的链表部分直接连接到当前合并链表的末尾
        last.next = cur1 != null ? cur1 : cur2;
        return shead;
    }
}
